Dijkstra's Algorithm combines initialization, greedy selection, and edge relaxation into a complete shortest path solution.

  • Initialization: Set $d[source]=0$ and all other distances to $\infty$. Push $(0, source)$ onto the Priority Queue (PQ).
  • Main Loop: Continuously extract the node $u$ with the smallest current distance $d[u]$ from the PQ until the PQ is empty.
  • Greedy Selection: Once a node $u$ is extracted, its shortest path is finalized. We immediately add $u$ to the visited set.
  • Stale Path Check: Skip processing if the extracted node $u$ has already been visited, preventing redundant work from older, worse paths.
  • Relaxation: For every unvisited neighbor $v$, check if the path through $u$ ($d[u] + w(u, v)$) is shorter than the current $d[v]$.
  • Update PQ: If relaxation occurs, update $d[v]$ and push the new, shorter distance $(d[v], v)$ onto the PQ for later processing.
Dijkstra's Algorithm Loop (Python Pseudo-code)

1initialize_distances(source)
2pq = [(0, source)]  # (distance, node)
3visited = set()
4
5while pq:
6    dist, u = heappop(pq)
7    if u in visited:
8        continue
9    visited.add(u)
10
11    for v, weight in graph[u].items():
12        if dist + weight < distances[v]:
13            distances[v] = dist + weight
14            heappush(pq, (distances[v], v))
15
16return distances